#include"DoubleLinkList.h"
#include<iostream>

DoubleLinkList::DoubleLinkList():size(0)
{
     head=tail= new Node(0);
     Free=nullptr;
}

DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    size=list.size;
    head=tail=new Node(0);
    Node *tp=head;
    Node *travePoint=list.head->next;
    while(travePoint!=nullptr)
    {
        Node *newNode=new Node(travePoint->value);
        tail=newNode;
        tp->next=newNode;
        newNode->prev=tp;
        tp=tp->next;
        travePoint=travePoint->next;
    }
}

DoubleLinkList &DoubleLinkList::operator=(const DoubleLinkList &list)
{
     while(head!=nullptr)
    {
        Node *nextNode=head->next;//下个节点存下
        delete head;
        head=nextNode;
    }
    tail=nullptr;
    size=list.size;
    head=tail=new Node(0);
    Node *tp=head;
    Node *travePoint=list.head->next;
    while(travePoint!=nullptr)
    {
        Node *newNode=new Node(travePoint->value);
        tail=newNode;
        tp->next=newNode;
        newNode->prev=tp;
        tp=tp->next;
        travePoint=travePoint->next;
    }
    

   return *this;
}

DoubleLinkList::~DoubleLinkList()
{
     while(head!=nullptr)
    {
        Node *nextNode=head->next;//下个节点存下
        if(Free)
        {
        Free(head->value);
        }
        delete head;
        head=nextNode;
    }
    tail=nullptr;
}

void DoubleLinkList::InsertTail(const ElementType &element)//O(1)
{
    Node *newNode=new Node(element);
    tail->next=newNode;
    newNode->prev=tail;
    tail=newNode;
    size++;
}

void DoubleLinkList::InsertHead(const ElementType &element)
{
    Node *newNode=new Node(element);//创建一个新节点
    newNode->next=head->next;
    newNode->prev=head;
    if(size>0)//防止当有且仅有head结点时，对head->next->prev操作会发生段错误
        newNode->next->prev=newNode;
    head->next=newNode;//插入节点
    size++;

}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element)
{
      if(index>size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head;//head-index，落到index-1位置
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    Node *newNode=new Node(element);
    newNode->next=travePoint->next;
    newNode->prev=travePoint;
    travePoint->next=newNode;
    if(size!=0)
        newNode->next->prev=newNode;
    size++;

}

void DoubleLinkList::RemoveByindex(size_t index)
{
     if(index>size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head;
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    Node *FreeNode=travePoint->next;
    travePoint->next=FreeNode->next;
    if(FreeNode->next!=nullptr)//重要一步，不进行判定可能会导致因为对空指针进行操作而产生的段错误
        FreeNode->next->prev=travePoint;
    else
        tail=travePoint;
    Free(FreeNode->value);
    delete FreeNode;
    size--;

}

void DoubleLinkList::RemoveByelement(const ElementType &element)
{
    Node *travePoint=head;
    while(travePoint->next!=nullptr)//遍历
    {
        if(Compare(travePoint->next->value,element))//找到待删除元素
        {
            Node *freeNode=travePoint->next;
            travePoint->next=freeNode->next;
            freeNode->next->prev=travePoint;
            delete freeNode;
            size--;
        }
        else
            travePoint=travePoint->next;//没找到，指针指向下一个节点，找到，原地踏步，下次删除就不会跳一个
    }
    

}

DoubleLinkList::ElementType *DoubleLinkList::FindByIndex(size_t index)
{
          if(index>=size)
    {   
        return  nullptr;
    }
    Node *travePoint=head->next;//head->next-index，落到index位置
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
        return &travePoint->value;
   
}

// DArray::DynamicArray DoubleLinkList::FindElement(const ElementType &element)
// {
//     DArray:: DynamicArray array;
//     Node *travePoint=head->next;
//     while(travePoint!=nullptr)
//     {
//         if(Compare(travePoint->next->value,element))
//             array.Inserttail(&travePoint->value);
        
//         travePoint=travePoint->next;
//     }
//         return array; 

   
// }

void DoubleLinkList::UpdateByindex(size_t index, const ElementType &elelment)
{
         if(index>=size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head->next;
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    travePoint->value=elelment;
}

void DoubleLinkList::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
     Node *travePoint=head->next;
    while(travePoint!=nullptr)
    {
        if(Compare( travePoint->value,oldvalue))
                travePoint->value=newvalue;
        
        travePoint=travePoint->next;
    }

}

void DoubleLinkList::Sort()
{
    FastSort(head->next,tail);
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{   if(start==end)
        return;
    Node *left=start;
    Node *right=end;
    ElementType temp=left->value;
    while(left!=right)
    {
        while(ComBig( right->value,temp)&&left!=right)
            right=right->prev;
        if(left!=right)
        {
            std::swap(left->value,right->value);
            left=left->next;
        }
        while(ComBig( temp,left->value)&&left!=right)
            left=left->next;
        if(left!=right)
        {
            std::swap(right->value,left->value);
            right=right->prev;
        }
    }
  left->value=temp;
   //这里的判断条件非常重要，在left或right到达临界时，理应停止递归，不加判断条件，会发生对空指针操作的段错误。
   if(start!=left)  FastSort(start,left->prev);
   if(right!=end)   FastSort(right->next,end);   
}

void DoubleLinkList::show()
{
    std::cout<<"size: "<<size<<std::endl;
    Node *travePoint=head->next;
    while(travePoint!=nullptr)//还没有结束
    {
            Print(travePoint->value);
            travePoint=travePoint->next;//遍历指针往后走
    }
    std::cout<<std::endl;
    travePoint=tail;
       while(travePoint!=head)//还没有结束,不把头打印
    {
            Print(travePoint->value);
            travePoint=travePoint->prev;//遍历指针往前走
    }
    std::cout<<std::endl;
}
